#include <iostream>
#include <random>
#include <cmath>
#include <ctime>
#include <vector>
#include <algorithm>
/*要求我们计算给定序列的最小和问题
即计算每一个元素前面小于当前元素的元素和是多少*/
using namespace std;
/*暴力法求解最小和问题*/
int violence_Sum(std::vector<int>& v)
{
	int sum = 0;
	for (int i = 1; i < v.size(); ++i)
	{
		/* code */
		for (int j = 0; j < i; ++j)
		{
			/* code */
			if(v[j]<v[i])
				sum+=v[j];
		}
	}
	return sum;
}
/*二路归并求最小和问题*/
class mergeSort
{
	friend class comparator;
public:
	mergeSort();
	~mergeSort();
	static int merge(std::vector<int> &v,size_t left,size_t mid,size_t right);
	static int sort(std::vector<int> &v,size_t low,size_t high);
};
int mergeSort::sort(std::vector<int> &array,size_t low,size_t high){
	if(low==high)		//一定要记得加递归基，太TMD操蛋了
		return 0;
	if (low<high)
	{
		size_t mid = low + ((high-low)>>1);		//更加安全，可以防止数组过大发生溢出
		return sort(array,low,mid)+sort(array,mid+1,high)+merge(array,low,mid,high);
	}
}
int mergeSort::merge(std::vector<int> &array,size_t low,size_t mid,size_t high){
	int res=0;
	std::vector<int> help;
	size_t p1=low;
	size_t p2=mid+1;
	while(p1<=mid&&p2<=high){
		res += array[p1]<array[p2]?array[p1]*(high-p2+1):0;
		cout<<res<<endl;
		int value = array[p1]<array[p2]?array[p1++]:array[p2++];	//这样代码量减少了，但算法不稳定了
		help.push_back(value);
	}
	while(p1<=mid){
		help.push_back(array[p1++]);
	}
	while(p2<=high){
		help.push_back(array[p2++]);
	}
	auto ivec=array.begin()+low;
	for(auto value:help){
		*ivec = value;		//可合并为*ivec++=value;
		ivec++;
	}
	return res;
}
//传说中的对数器   
class MinSum 
{
public:
	std::vector<int> geneArr()
	{
		static default_random_engine e(time(0));
//		umofminNum_Mergesort_1.cpp***  tatic uniform_int_distribution<int> u(-1000,10000);
//		std::vector<int> v;
//		for(size_t i=0;i<abs(u(e)%100);i++){
//			v.push_back(u(e));
//		}
		static uniform_int_distribution<int> u(1,10);//设个小的，进行人工计算
		std::vector<int> v;
		for(size_t i=0;i<7;i++){
		v.push_back(u(e));
		}
		return v;
	}
	void operator()(){
		std::vector<int> array1 = geneArr();
		std::vector<int> array2(array1);
		for(auto value:array2){
			cout<<value<<" ";
		}
		cout<<endl;
		int sum1=violence_Sum(array1);
		cout<<sum1<<endl;
		int sum2 = mergeSort::sort(array2,0,array2.size()-1);
		cout<<sum2<<endl;
	}
};

int main(){
	MinSum comparator;
	comparator();
	return 0;
}
